package demo.practice.trie;

import java.util.*;


class P212Trie {

    Map<Character, P212Trie> child = new HashMap<>();
    int height = 0;
    Map<String, P212Trie> map = new HashMap<>();
    Map<String,P212Trie> topset = new HashMap<>();

    private void insert(char[][] board, int i, int j, Set<String> set, P212Trie t) {
        if (set.contains(i + "_" + j) || t.height >= 10)
            return;

        if (t.child.get(board[i][j]) == null) {
            P212Trie ch = new P212Trie();
            ch.height = t.height + 1;
            t.child.put(board[i][j], ch);
            if(height==0){
                topset.put(i + "_" + j,t.child.get(board[i][j]));
            }
        } else {
            //不处理
            t.child.get(board[i][j]).height=t.height + 1; //但需要更新完深度
        }


        set.add(i + "_" + j);

        if (i + 1 < board.length)    //下
        {
            Set<String> set1 = new HashSet<>(set);
            set1.add(i + "_" + j);
            insert(board, i + 1, j, set1, t.child.get(board[i][j]));
        }

        if (i - 1 >= 0)    //上
        {
            Set<String> set1 = new HashSet<>(set);
            set1.add(i + "_" + j);
            insert(board, i - 1, j, set1, t.child.get(board[i][j]));
        }

        if (j + 1 < board[i].length)    //右
        {
            Set<String> set1 = new HashSet<>(set);
            set1.add(i + "_" + j);
            insert(board, i, j + 1, set1, t.child.get(board[i][j]));
        }

        if (j - 1 >= 0)    //左
        {
            Set<String> set1 = new HashSet<>(set);
            set1.add(i + "_" + j);
            insert(board, i, j - 1, set1, t.child.get(board[i][j]));
        }
    }


    public void insert(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                insert(board, i, j, new HashSet<>(), this);
            }
        }

    }

    public boolean serach(String word) {

        P212Trie cur = this;
        for (char c : word.toCharArray()) {
            if (cur.child.get(c) == null)
                return false;
            cur = cur.child.get(c);
        }

        return true;
    }

}

public class P212 {
    public static void main(String[] args) {

        P212 p212 = new P212();
        long start = System.currentTimeMillis();
        //p212.findWords(new char[][]{{'o','a','a','n'},{'e','t','a','e'},{'i','h','k','r'},{'i','f','l','v'}},new String[]{"oath"} );
        List<String> words = p212.findWords(new char[][]{{'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a'}, {'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a'}, {'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a'}, {'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a'}, {'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a'}, {'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a'}, {'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a'},
                {'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a'}, {'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a'},
                {'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a'}, {'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a'},
                {'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a'}}, new String[]{"a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa", "aaaaaaaaa", "aaaaaaaaaa"});

        /**
         * [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
         * ["eat"]
         */
        //List<String> words = p212.findWords(new char[][]{{'o', 'a', 'a', 'n'}, {'e', 't', 'a', 'e'}, {'i', 'h', 'k', 'r'}, {'i', 'f', 'l', 'v'}}, new String[]{"eat"});
        System.out.println(words);
        System.out.println(System.currentTimeMillis() - start);

    }

    public List<String> findWords(char[][] board, String[] words) {

        P212Trie t = new P212Trie();
        long start = System.currentTimeMillis();
        t.insert(board);
        // System.out.println(System.currentTimeMillis() - start);
        List<String> list = new ArrayList<>();

        for (String word : words) {
            if (t.serach(word))
                list.add(word);
        }
        //System.out.println(System.currentTimeMillis() - start);
        return list;
    }

}
